package com.sise.Stack;

/**
 *      剑指 Offer 09. 用两个栈实现队列
 *
 *      用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
 *      分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
 */

import java.util.LinkedList;

public class _offer_09_CQueue {

    public _offer_09_CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

    public void appendTail(int value) {
        stack1.add(value);
    }

    // 如果栈2 不为空，那么就输出栈2的最后一位数值。否则判断栈1中是否有值，有则将 栈1尾部 添加到栈2的尾部
    public int deleteHead() {
        if (!stack2.isEmpty()) return stack2.removeLast();
        if (stack1.isEmpty()) return -1;

        while (!stack1.isEmpty()){                      // 这里的遍历添加其实是 两个栈之间数据的倒叙转换
            stack2.addLast(stack1.removeLast());
        }
        return stack2.removeLast();
    }
}
/**
 *      ｜3｜     ｜1｜     栈1遍历倒叙赋值，拿栈1的尾部 [3]，赋值给栈2的头部，
 *      ｜2｜     ｜2｜     栈1拿 [2] 出来，栈2 addLast 添加到尾部，那么此时 2 是在 3 后面，
 *      ｜1｜     ｜3｜     从栈2的角度来看，那么 2 就在 3 上面，故此 removeLast 便是先移走栈顶元素
 *       ——       ——
 */